package org.example.myleet.p897;

import org.example.myleet.Utils.TreeNode;

/**
 * 0 ms
 * Morris中序遍历
 */
public class Solution {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode(-1);
        TreeNode head = dummy;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode prev = cur.left;
                while (prev.right != null && prev.right != cur) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    prev.right = cur;
                    cur = cur.left;
                } else {
                    prev.right = null;
                    head.right = new TreeNode(cur.val);
                    head = head.right;
                    cur = cur.right;
                }
            } else {
                head.right = new TreeNode(cur.val);
                head = head.right;
                cur = cur.right;
            }
        }
        return dummy.right;
    }
}
